package com.wenhao.leetcode.hard;

/**
 * 题目：https://leetcode-cn.com/problems/edit-distance/
 * 编辑距离
 *
 * 我就是不理解，这一题是怎么想到要用动态规划做的？？？
 *
 * 最令我震惊的，就是这一题是动态规划还有正则表达式是动态规划。。。
 *
 * @author Wenhao Tong
 * @create 2021-07-11 19:43
 */
public class LeetCode72 {

    public static void main(String[] args) {

    }

    public int minDistance(String word1, String word2) {
        int[][] results = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0;i < results[0].length;i++) {
            results[0][i] = i;
        }
        for (int i = 0;i < results.length;i++) {
            results[i][0] = i;
        }
        for (int i = 1;i <= word1.length();i++) {
            for (int j = 1;j < word2.length();j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    results[i][j] = Math.min(results[i - 1][j] + 1,Math.min(results[i][j - 1] + 1,results[i - 1][j - 1]));
                } else {
                    results[i][j] = 1 + Math.min(results[i - 1][j],Math.min(results[i][j - 1],results[i - 1][j - 1]));
                }
            }
        }
        return results[word1.length()][word2.length()];
    }
}
